<?php

/**
 * 快速排序: 使用了二分的思想,让每次的比较不再只是两个相邻的元素一个一个地比较。所以它的平均时间复杂度可以提升到 O(NlogN) 的级别。
 */

function QuickSort(&$arr, $start, $end) {
    if ($start > $end) {
        return;
    }
    $key = $arr[$start];
    $left = $start;
    $right = $end;

    while ($left < $right) {
        // 右边下标确定
        while ($left < $right && $arr[$right] >= $key) {
            $right--;
        }
        // 左边下标确定
        while ($left < $right && $arr[$left] <= $key) {
            $left++;
        }
        if ($left < $right) { // 交换步骤
            $tmp = $arr[$left];
            $arr[$left] = $arr[$right];
            $arr[$right] = $tmp;
        }
        // echo $left, ',', $right, PHP_EOL;
    }

    $arr[$start] = $arr[$left];
    $arr[$left] = $key;

    // 递归左右两边继续, 分治的思想
    QuickSort($arr, $start, $right - 1);
    QuickSort($arr, $right + 1, $end);
}

$numbers = [49, 38, 65, 97, 76, 13, 27, 49];
echo "原始数据: " . implode(', ', $numbers), PHP_EOL;

QuickSort($numbers, 0, count($numbers) - 1);
echo "快速排序结果: " . implode(',', $numbers), PHP_EOL;
//13, 27, 38, 49, 49, 65, 76, 97